package com.leetcode.LC_MED;

public class LC279_3 {
    int times = Integer.MAX_VALUE;

    public int numSquares(int n) {
        // 对一个数进行开方，将数字的平方存入此数组即可
        int num = (int) Math.sqrt(n);
        int[] res = new int[num];
        for (int i = 1; i <= num; i++) {
            res[i - 1] = i * i;
        }
        findRes(n, res, res.length - 1, 0);
        return times;
    }

    private void findRes(int n, int[] res, int index, int time) {
        if (index < 0 || times <= time + n / res[index]) {
            return;
        }
        if (n % res[index] == 0) {
            times = Math.min(times, time + n / res[index]);
            return;
        }
        for (int i = n / res[index]; i >= 0; i--) {
            findRes(n - i * res[index], res, index - 1, time + i);
        }
    }

    public static void main(String[] args) {
        LC279_3 lc279_3 = new LC279_3();
        System.out.println(lc279_3.numSquares(12));
    }
}
